package 牛客.动态规划;

import java.util.ArrayList;

public class NC325不同路径的数目_二 {
    public int uniquePathsWithObstacles (ArrayList<ArrayList<Character>> obstacleGrid) {
        // write code here
        int row=obstacleGrid.size();
        int column=obstacleGrid.get(1).size();

        if (obstacleGrid.get(0).get(0)=='1' || obstacleGrid.get(row-1).get(column-1)=='1') {
            return 0;
        }
        int[][] dp=new int[row][column];
        for (int i = 0; i <column && obstacleGrid.get(0).get(i)=='0'; i++) {
            dp[0][i]=1;
        }
        for (int i = 0; i <row && obstacleGrid.get(i).get(0)=='0'; i++) {
            //初始化第一列
            dp[i][0]=1;
        }

        for (int i = 1; i <row ; i++) {
            for (int j = 1; j <column ; j++) {
                if (obstacleGrid.get(i).get(j)=='1') continue;
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[row-1][column-1];

    }


    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //1为障碍物
        int row=obstacleGrid.length;
        int column=obstacleGrid[0].length;

        if (obstacleGrid[0][0]==1 || obstacleGrid[row-1][column-1]==1) {
            return 0;
        }

        //1.确定dp[i][j]的意义
        int[][] dp=new int[row][column];
        //3.对dp的第一行和第一列进行初始化
        for (int i = 0; i <column && obstacleGrid[0][i]==0 ; i++) {
            //初始化 第一行
            dp[0][i]=1;
        }
        for (int i = 0; i <row && obstacleGrid[i][0]==0 ; i++) {
            //初始化 第一列
            dp[i][0]=1;
        }

        for (int i = 1; i <row; i++) {
            for (int j = 1; j <column; j++) {
                dp[i][j]= obstacleGrid[i][j]==0 ? dp[i-1][j]+dp[i][j-1] : 0;
//                if (obstacleGrid[i][j]==1) continue;
//                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[row-1][column-1];

    }
}
